294. Делители

В интервале [L; U] найти число, которое имеет наибольшее количество делителей.

Вход. Первая строка содержит количество тестов n. Каждая из следующих n строк содержит два числа L и U – границы интервала (1 £ L £ U £ 1000000000, 0 £ U – L £ 10000).

Выход. Для каждого теста вывести число из интервала [L; U], которое имеет наибольшее количество делителей.

Пример входа

3

1 10

1000 1000

999999900 1000000000

Пример выхода

Between 1 and 10, 6 has a maximum of 4 divisors.

Between 1000 and 1000, 1000 has a maximum of 16 divisors.

Between 999999900 and 1000000000, 999999924 has a maximum of 192 divisors.

РЕШЕНИЕ

разложение на множители + перебор

Анализ алгоритма

Следует перебрать все числа интервала [L; U], для каждого вычислить количество его делителей. Число, имеющее наибольшее число делителей, вывести на печать.

Если n = , то число n имеет (a₁ + 1) * (a₂ + 1) * … * (a_k + 1) делителей.

Реализация алгоритма

Функция count_divisors(n) вычисляет количество делителей числа n по выше приведенной формуле.

int count_divisors(int n)

{

int c, i, res=1;

for(i = 2; i <= (int)sqrt(n); i++)

{

if (n % i == 0)

{

c = 0;

while(n % i == 0) n /= i, c++;

res *= (c + 1);

}

}

if (n > 1) res *= 2;

return res;

}

Основной цикл программы. Читаем количество тестов tests.

scanf("%d",&tests);

while(tests--)

{

Вводим границы интервала l и u.

scanf("%d %d",&l,&u);

Для каждого числа i от l до u вычисляем в переменной c количество его делителей. Максимальное количество делителей res будет содержать число n.

res = 0;

for(i = l; i <= u;i++)

{

c = count_divisors(i);

if (c > res) res = c, n = i;

}

Выводим результат.

printf("Between %d and %d, %d has a maximum of %d divisors.\n",l,u,n,res);

}